PGCon2012 - Final Release
PGCon 2012
The PostgreSQL Conference
| Speakers | |
|---|---|
|
Alexander Korotkov |
| Schedule | |
|---|---|
| Day | Talks - 2 - Friday - 2012-05-18 |
| Room | MRT 212 |
| Start time | 15:00 |
| Duration | 01:00 |
| Info | |
| ID | 383 |
| Event type | Lecture |
| Track | Advanced Features |
| Language used for presentation | English |
Index support for regular expression search
Regular expressions (regex) are powerful tool for text processing. When dealing with large string collections it's important to search fast on that collections (i.e. search using index). Indexing for regex search is a quite hard task. This talk presents novel technique (and WIP patch for PostgreSQL implementing it) for regex search using trigram indexes. Proposed technique provides more comprehensive trigram extraction than analogues, i.e. higher performance.
There are two existed approaches for index-based regex search. The FREE indexing engine is based on extractions continued text fractions from regex and perform substring search. Google Code Search approach present more sophisticated recursive analysis of regex with extraction of various regex attributes. This talk presents novel technique of regex analysis which is based on automata transformation rather than original regex analysis. Superiority of proposed technique will be proved by examples and tests.
The talk would be organized as following:
- Introduction.
- Regular expressions
- Finite automata
- pg_trgm contrib module
- Existing techniques for index-based regular expression search
- FREE indexing engine
- Google Code Search
- Proposed technique
- Description
- Examples
- Comparison with analogues
- Limitations
- Performance results